from typing import List


class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        length = len(s)
        c = []
        for i in range(length):
            c.append(i)

        def find(x):
            if c[x] == x:
                return x
            else:
                c[x] = find(c[x])
                return c[x]

        def merge(i, j):
            x = find(i)
            y = find(j)

            c[x] = y

        for pair in pairs:
            merge(pair[0], pair[1])

        for i in range(length):
            find(i)

        dic = {}  # {0:[(a,1)]}
        index_dic = {}
        for i in range(len(c)):
            dic.setdefault(c[i], [])
            dic[c[i]].append(s[i])
            index_dic.setdefault(c[i], [])
            index_dic[c[i]].append(i)

        for key in dic:
            dic[key].sort()
            index_dic[key].sort()

        print(dic)
        new_arr = [""] * length
        for type_, arr in dic.items():
            for i in range(len(arr)):
                index = index_dic[type_][i]
                new_arr[index] = arr[i]

        print(new_arr)
        return "".join(new_arr)


if __name__ == "__main__":

    s = "dcab"
    pairs = [[0, 3], [1, 2]]

    Solution().smallestStringWithSwaps(s, pairs)
